#include "sort.h"
#include "heap.h"
#include <gtest/gtest.h>

void sort_nums(std::vector<int> &nums,
               std::function<void(std::vector<int> &)> function) {
  function(nums);
}

/**
 * @brief 冒泡排序
 * @note 循环比较相邻元素的大小，每次循环都将大的元素移动到后面
 */
void bubble_sort(std::vector<int> &nums) {

  const int n = nums.size();
  for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < n - i - 1; ++j) {
      if (nums[j] > nums[j + 1])
        std::swap(nums[j], nums[j + 1]);
    }
  }
}

/**
 * @brief 插入排序
 * @note 将数组分为已排序和未排序两组，每次从未排序的部分取出第一个元素
 *       插入到已排序的部分中
 */
void insert_sort(std::vector<int> &nums) {
  const int n = nums.size();
  // i 左侧已排序，右侧未排序
  for (int i = 1; i < n; ++i) {
    int num = nums[i];
    int j = i - 1;
    while (j >= 0 && nums[j] >= num) {
      nums[j + 1] = nums[j];
      --j;
    }
    nums[j + 1] = num;
  }
}
/**
 * @brief 希尔排序
 * @note 插入排序的优化，每隔gap的元素分为一组并进行插入排序
 *       然后逐步缩小gap
 */
void shell_sort(std::vector<int> &nums) {
  const int n = nums.size();

  for (int gap = n / 2; gap > 0; gap /= 2) { // 分组，每次缩小一般

    for (int i = gap; i < n; ++i) {
      int tmp = nums[i];
      int j = i - gap;
      while (j >= 0 && nums[j] >= tmp) {
        nums[j + gap] = nums[j];
        j -= gap;
      }
      nums[j + gap] = tmp;
    }
  }
}

/**
 * @brief 选择排序
 * @note 每次从未排序的部分选择最小的并交换
 */
void select_sort(std::vector<int> &nums) {
  const int n = nums.size();

  for (int i = 0; i < n - 1; ++i) {
    int min_idx = i;
    for (int j = i + 1; j < n; ++j) {
      if (nums[j] < nums[min_idx]) {
        min_idx = j;
      }
    }
    std::swap(nums[i], nums[min_idx]);
  }
}

/**
 * @brief 归并排序
 * @note
 */
void merge_sort(std::vector<int> &nums) {
  const int n = nums.size();
  merge(nums, 0, n - 1);
}

/**
 * @brief 快速排序
 */
void quick_sort(std::vector<int> &nums) {
  const int n = nums.size();
  quick_sort_recursion(nums, 0, n - 1);
}

/**
 * @brief 堆排序
 * @note 通过构建小根堆实现，可以直接原地修改，降低空间复杂度
 */
void heap_sort(std::vector<int> &nums) {
  const int n = nums.size();
  // 1. 使用构造函数,下沉操作 
  // heap h(nums);
  // 2. 使用默认构造函数，上浮操作
  heap h;
  for(int num : nums)
    h.insert(num);
  std::vector<int> tmp;
  while (!h.empty()) {
    tmp.push_back(h.top());
    h.pop();
  }
  std::copy(tmp.begin(), tmp.end(), nums.begin());
}

/**
 * @brief 计数排序
 * @attention 假设nums均为整数
 * @note  https://www.runoob.com/w3cnote/counting-sort.html
 */
void counting_sort(std::vector<int>& nums){
  const int n = nums.size();
  int max_value = *std::max_element(nums.begin(),nums.end());
  std::vector<int> cnt(max_value+1,0);

  // 计数，统计每个元素出现的次数
  for(int num : nums){
    ++cnt[num];
  }
  // 统计每个元素前面的元素个数
  for(int i = 1; i < cnt.size(); ++i){
    cnt[i] += cnt[i-1];
  }

  std::vector<int> tmp(n,0);
  for(int num : nums){
    tmp[cnt[num] - 1] = num;
    --cnt[num];
  }
  std::copy(tmp.begin(),tmp.end(),nums.begin());
}

/**
 * @brief 桶排序
 * @note 将元素分装到不同的桶中，单独对每个桶排序，然后组合
 */
void bucket_sort(std::vector<int>& nums){
  int max_value = *std::max_element(nums.begin(),nums.end());
  int min_value = *std::min_element(nums.begin(),nums.end());
  const int bucket_size = 10;
  const int cnt = (max_value-min_value)/bucket_size + 1;
  std::vector<std::vector<int>> buckets(cnt);

  // 装桶
  for(int num : nums){
    int bucket_id = (num-min_value)/bucket_size;
    buckets[bucket_id].push_back(num);
  }

  // 对每个桶排序
  int it = 0;
  for(auto& bucket : buckets){
    sort(bucket.begin(),bucket.end());
    std::copy(bucket.begin(),bucket.end(),nums.begin()+it);
    it += bucket.size();
  }
}

/**
 * @brief 基数排序
 * @note 对每个元素的每一位进行排序，然后逐渐收敛到最终结果
 * @ref https://www.runoob.com/w3cnote/radix-sort.html
 */
void radix_sort(std::vector<int> &nums){

  // 1.统计数组中最大的元素及其位数
  int max_value = *std::max_element(nums.begin(),nums.end());
  int bits = 1;
  while(max_value >= 10){
    ++bits;
    max_value /= 10;
  }

  // 按位数排序
  const int n = nums.size();
  int radix = 1; // 从个位开始
  std::vector<int> buckets(10); // 计数排序，统计出现次数

  for(int i = 0; i < bits; ++i){
    
    std::fill(buckets.begin(),buckets.end(),0);
    // 统计元素在radix上出现的次数
    for(int num : nums){
      int bit = (num/radix)%10;
      ++buckets[bit];
    }
    // 与计数排序类似(按位排序)
    for(int j = 1; j < buckets.size(); ++j){ 
      buckets[j] += buckets[j-1];
    }
    std::vector<int> tmp(n,0);
    for(int j = nums.size()-1; j >= 0; --j){
      int num = nums[j];
      int bit = (num/radix)%10;
      tmp[buckets[bit]-1] = num;
      --buckets[bit];
    }
    std::copy(tmp.begin(),tmp.end(),nums.begin());
    radix *= 10;
  }
}






// utils function
void merge(std::vector<int> &nums, int left, int right) {
  if (left >= right)
    return;
  // 分治
  int mid = (left + right) / 2;
  merge(nums, left, mid);
  merge(nums, mid + 1, right);

  // 合并
  std::vector<int> tmp;
  int i = left, j = mid + 1;
  while (i <= mid && j <= right) {
    if (nums[i] < nums[j]) {
      tmp.push_back(nums[i]);
      ++i;
    } else {
      tmp.push_back(nums[j]);
      ++j;
    }
  }
  while (i <= mid) {
    tmp.push_back(nums[i]);
    ++i;
  }
  while (j <= right) {
    tmp.push_back(nums[j]);
    ++j;
  }
  std::copy(tmp.begin(), tmp.end(), nums.begin() + left);
}

void quick_sort_recursion(std::vector<int> &nums, int left, int right) {
  if (left >= right)
    return;

  int pivot = nums[right];

  int low = left, high = right;
  while (low < high) {
    while (low < high && nums[low] <= pivot)
      ++low;
    nums[high] = nums[low];
    while (low < high && nums[high] >= pivot)
      --high;
    nums[low] = nums[high];
  }
  nums[low] = pivot;

  quick_sort_recursion(nums, left, low - 1);
  quick_sort_recursion(nums, low + 1, right);
}